﻿using System;
using System.Collections.Generic;
using System.Text;


public class BiTree<T>
{
    private TreeNode<T> head; // 头引用
    public TreeNode<T> Head { get { return head; } set { head = value; } }

    public BiTree()
    {
        head = null;
    }

    public BiTree(T val)
    {
        TreeNode<T> p = new TreeNode<T>(val);
        head = p;
    }

    public BiTree(T val, TreeNode<T> lp, TreeNode<T> rp)
    {
        TreeNode<T> p = new TreeNode<T>(val, lp, rp);
        head = p;
    }

    // 判断是否为空二叉树
    public bool IsEmpty()
    {
        if (head == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    // 获取根结点
    public TreeNode<T> Root()
    {
        return head;
    }

    // 获取结点的左孩子结点
    public TreeNode<T> GetLChild(TreeNode<T> p)
    {
        return p.LChild;
    }

    // 获取结点的右孩子结点
    public TreeNode<T> GetRChild(TreeNode<T> p)
    {
        return p.RChild;
    }

    // 将结点p的左子树插入值为val的新结点
    // 原来的左子树成为新结点的左子树
    public void InsertL(T val, TreeNode<T> p)
    {
        TreeNode<T> tmp = new TreeNode<T>(val);
        tmp.LChild = p.LChild;
        p.LChild = tmp;
    }

    // 将结点p的右子树插入值为val的新结点
    // 原来的右子树成为新结点的右子树
    public void InsertR(T val, TreeNode<T> p)
    {
        TreeNode<T> tmp = new TreeNode<T>(val);
        tmp.RChild = p.RChild;
        p.RChild = tmp;
    }

    // 若 p 非空，删除p的左子树
    public TreeNode<T> DeleteL(TreeNode<T> p)
    {
        if ((p == null) || (p.LChild == null))
        {
            return null;
        }

        TreeNode<T> tmp = p.LChild;
        p.LChild = null;
        return tmp;
    }

    // 若 p 非空，删除p的右子树
    public TreeNode<T> DeleteR(TreeNode<T> p)
    {
        if ((p == null) || (p.RChild == null))
        {
            return null;
        }

        TreeNode<T> tmp = p.RChild;
        p.RChild = null;
        return tmp;
    }

    // 判断是否是叶子结点
    public bool IsLeaf(TreeNode<T> p)
    {
        if ((p != null) && (p.LChild == null) && (p.RChild == null))
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    // 先序遍历，先根结点后左右子树
    public void PreOrder(TreeNode<T> root)
    {
        if (root == null)
        {
            return;
        }

        // 处理根结点
        Console.WriteLine("{0}", root.Data);
        // 先序遍历左子树
        PreOrder(root.LChild);
        // 先序遍历右子树
        PreOrder(root.RChild);
    }

    // 中序遍历，先左子树 然后根结点 最后右子树
    public void InOrder(TreeNode<T> root)
    {
        if (root == null)
        {
            return;
        }

        // 中序遍历左子树
        InOrder(root.LChild);

        // 处理根结点
        Console.WriteLine("{0}", root.Data);

        // 中序遍历右子树
        InOrder(root.RChild);
    }

    // 后序遍历，先左右子树再根结点
    public void PostOrder(TreeNode<T> root)
    {
        if (root == null)
        {
            return;
        }

        // 后序遍历左子树
        PostOrder(root.LChild);

        // 后序遍历右子树
        PostOrder(root.RChild);

        // 处理根结点
        Console.WriteLine("{0}", root.Data);
    }

    // 层序遍历，一层层结点遍历
    public void LevelOrder(TreeNode<T> root)
    {
        if (root == null)
        {
            return;
        }

        // 设置一个队列保存层序遍历的结点
        CSeqQueue<TreeNode<T>> sq = new CSeqQueue<TreeNode<T>>(50);

        // 根结点入队
        sq.In(root);

        while (!sq.IsEmpty())
        {
            // 结点出队
            TreeNode<T> tmp = sq.Out();
            // 处理当前结点
            Console.WriteLine("{0}", tmp.Data);
            // 当前结点的左孩子结点入队
            if (tmp.LChild != null)
            {
                sq.In(tmp.LChild);
            }
            // 当前结点的右孩子结点入队
            if (tmp.RChild != null)
            {
                sq.In(tmp.RChild);
            }
        }
    }
}
